package Offer03_数组中重复的数字;

import java.util.HashSet;

/**
 * ------------------------------------------------------------------------------------
 * 题目：
 *      找出数组中重复的数字。
 *      在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
 *      数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
 *      请找出数组中任意一个重复的数字。
 * ------------------------------------------------------------------------------------
 * 示例：
 *      输入：
 *          [2, 3, 1, 0, 2, 5, 3]
 *      输出：2 或 3
 * -----------------------------------------------------------------------------------
 * 方法：
 *      方法1：使用哈希集合存储元素
 *              时间复杂度O(N),空间复杂度也是O(N)
 *      方法2：模拟哈希集合
 *              时间复杂度O(N),空间复杂度是O(1)
 *      方法3：将元素转移到元素所在下标的位置
 *              时间复杂度O(N),空间复杂度是O(1)
 * ----------------------------------------------------------------------------------
 */
class Solution {
    public static void main(String[] args) {
        int[] nums1 = new int[]{2,3,1,0,2,5,3};
        int[] nums2 = new int[]{2,3,1,0,2,5,3};
        int[] nums3 = new int[]{2,3,1,0,2,5,3};
        System.out.println(findRepeatNumber1(nums1));
        System.out.println(findRepeatNumber2(nums2));
        System.out.println(findRepeatNumber3(nums3));
    }
    public static int findRepeatNumber1(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int x:nums){
            if(set.contains(x)){
                return x;
            }else{
                set.add(x);
            }
        }
        return -1;
    }
    public static int findRepeatNumber2(int[] nums) {
        int n;
        for(int i=0;i<nums.length;++i){
            if(nums[i]>=0){
                n=nums[i];
            }else{
                n=nums[i]+nums.length;
            }
            if(nums[n]>=0){
                nums[n]-=nums.length;
            }else{
                return n;
            }
        }
        return -1;
    }
    public static int findRepeatNumber3(int[] nums) {
        for(int i=0;i<nums.length;++i){
            while(nums[i]!=i){
                if(nums[i]==nums[nums[i]]){
                    return nums[i];
                }
                int tmp = nums[nums[i]];
                nums[nums[i]]=nums[i];
                nums[i]=tmp;
            }
        }
        return -1;
    }
}
